package main

import (
	"fmt"
	"math/rand"
)

func QuickSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	pivotIndex := rand.Intn(len(arr))
	pivot := arr[pivotIndex]
	arr[0], arr[pivotIndex] = arr[pivotIndex], arr[0]

	left := make([]int, 0)
	right := make([]int, 0)

	for i := 1; i < len(arr); i++ {
		if arr[i] < pivot {
			left = append(left, arr[i])
		} else {
			right = append(right, arr[i])
		}
	}

	return append(append(QuickSort(left), pivot), QuickSort(right)...)
}

func TestQuickSort() {
	arr := []int{5, 2, 8, 3, 9, 1}
	fmt.Println(arr)
	sortedArr := QuickSort(arr)
	fmt.Println(sortedArr)
}
